package com.lin.removenthnodefromendoflist;

/**
 * 删除链表倒数第n个节点
 *
 * @author 九分石人
 */
public class RemoveNthNodeFromEndofList {

    /**
     * 一次遍历法
     * Leetcode题解带坑，不考虑极限情况
     *
     * @param head 链表头节点
     * @param n    要删除的节点
     * @return 头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode first;
        ListNode second;
        ListNode third;

        first = head;
        second = head;
        third = head;
        if (n == 1 && head.next == null) {
            return null;
        }

//        for (int i = 0; i < n; i++) {
//            //此处规避掉删除头节点的情况，如果删除头节点，n与链表长度相等，后移语句必定空指针
//            //长度为n的链表只可移动n-1次
//            if (third.next != null) {
//                third = third.next;
//            } else {
//                return first.next;
//            }
//        }

//        与上面的注作用相同，提升效率
        for (int i = 0; i < n; i++) {
            third = third.next;
        }
        if (third == null) {
            return first.next;
        }

        while (third.next != null) {
            third = third.next;
            second = second.next;
        }
        second.next = second.next.next;
        return first;
    }


}
